import javax.swing.tree.TreeNode;

public class Main {
    public static void main(String[] args) {
        System.out.println("Hello world!");
    }

    //力扣226 翻转二叉树
        public TreeNode invertTree(TreeNode root) {
            if(root == null){
                return null;
            }
            //叶子节点直接返回节约时间
            if(root.left == null && root.right == null){
                return root;
            }

            //左子树与右子树交换
            TreeNode temp = null;
            temp = root.left;
            root.left = root.right;
            root.right = temp;

            //递归调用
            invertTree(root.left);
            invertTree(root.right);

            return root;
        }




    //力扣100. 相同的树
    public boolean isSameTree(TreeNode p, TreeNode q) {
            if(p == null && q == null){//都为空
                return true;
            }else if((p != null && q == null) || (p == null && q != null)){//其中一个为空
                return false;
            }else if(p.val == q.val){//根数据同
                return isSameTree(p.left, q.left) && isSameTree(p.right,q.right);
            }else{//根数据不同
                return false;
            }
        }

    //力扣572. 另一棵树的子树
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        //树相同
        if(isSameTree(root,subRoot)){
            return true;
        }
        //
        if(root == null && subRoot != null){
            return false;
        }
        return isSubtree(root.left, subRoot) || isSubtree(root.right,subRoot);
    }
}
import java.util.Scanner;
class  TreeNode{
    char val;
    TreeNode left;
    TreeNode right;
    public TreeNode(char val){
        this.val = val;
    }
}

//牛客KY11 二叉树遍历
// 注意类名必须为 Main, 不要有任何 package xxx 信息
//public class Main {
//    //创建树
//
//    private static int i = 0;
//
//    public  static void main(String[] args) {
//        Scanner in = new Scanner(System.in);
//        // 注意 hasNext 和 hasNextLine 的区别
//        while (in.hasNextLine()) { // 注意 while 处理多个 case
//            String st = in.nextLine();
//            TreeNode root = creatTree(st);
//            inOrder(root);
//        }
//    }
//    public static TreeNode creatTree(String st){
//        TreeNode root = null;
//
//        char ch = st.charAt(i);
//        if(ch != '#'){
//            root = new TreeNode(ch);
//            i++;
//            root.left = creatTree(st);
//            root.right = creatTree(st);
//        }else{
//            i++;
//        }
//        return root;
//    }
//    public static void inOrder(TreeNode root){
//        if(root == null){
//            return ;
//        }
//        inOrder(root.left);
//        System.out.print(root.val+" ");
//        inOrder(root.right);
//    }
//}
//力扣110. 平衡二叉树O(N^2)
/*
class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;
        }
        return Math.abs(getHeight(root.left) - getHeight(root.right)) <= 1
                && isBalanced(root.left) && isBalanced(root.right);
    }

    //求深度函数
    public int getHeight(TreeNode root){
        if(root == null){
            return 0;
        }
        int left = getHeight(root.left);
        int right = getHeight(root.right);
        return left > right ? left + 1 : right +1;
    }
}*/

//力扣110. 平衡二叉树O(N)
class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;
        }

        return getHeight(root) >= 0;
    }

    //求深度函数
    public int getHeight(TreeNode root){
        if(root == null){
            return 0;
        }
        int left = getHeight(root.left);
        if(left < 0){
            return -1;
        }
        int right = getHeight(root.right);
        if(left >= 0 && right >= 0 && Math.abs(left - right) <= 1){
            return left > right ? left + 1 : right +1;
        }else{
            return -1;

        }
    }
}